package com.cuz.二叉树;

class 二叉树中的最大路径和 {

    public static void main(String[] args) {


        //0 1 2
        //1 3 4
        //2 5 6
        //3 7 8
        //4 9,10
        //5 11,12
        //6 13 14
        //0,1,2,3, 4,5,  6,7,8,9, 10,  ,11, 12,  13
        //5,4,8,11,null,13,4,7,2,null,null,null,1
        TreeNode n5 = new TreeNode(5);
        TreeNode n4 = new TreeNode(4);
        TreeNode n8 = new TreeNode(8);
        TreeNode n11 = new TreeNode(11);
        TreeNode n13 = new TreeNode(13);
        TreeNode n4t = new TreeNode(4);
        TreeNode n7 = new TreeNode(7);
        TreeNode n2 = new TreeNode(2);
        TreeNode n1 = new TreeNode(1);
        n5.left = n4;
        n5.right = n8;
        n4.left = n11;
        n8.left = n13;
        n8.right = n4t;
        n11.left = n7;
        n11.right = n2;
       n4t.left =n1;

        System.out.println(new 二叉树中的最大路径和().maxPathSum(n5));
    }

    public int maxPathSum(TreeNode root) {
        if (root == null) {
            return 0;
        }
        if (root.right == null && root.left == null) {
            return root.val;
        }
        Info res = process(root);
        return Math.max(res.rootWith, res.rootWithout);
    }


    static class Info {


        int rootWithout;
        int rootWith;

        Info(int rootWithout, int rootWith) {
            this.rootWith = rootWith;
            this.rootWithout = rootWithout;
        }

    }


    private Info process(TreeNode node) {
        if (node == null) {
            return null;
        }

        Info rightInfo = process(node.right);
        Info leftInfo = process(node.left);

        //当前根节点参与到路径中
        int rWith = node.val;
        if (leftInfo != null && leftInfo.rootWith > 0) {
            rWith = rWith + leftInfo.rootWith;
        }
        if (rightInfo != null && rightInfo.rootWith > 0) {
            rWith = rWith + rightInfo.rootWith;
        }

        //当前根节点不参与到路径中
        int rWithout = Integer.MIN_VALUE;
        if (leftInfo != null) {
            rWithout = Math.max(rWithout, leftInfo.rootWith);
            rWithout = Math.max(rWithout, leftInfo.rootWithout);
        }
        if (rightInfo != null) {
            rWithout = Math.max(rWithout, rightInfo.rootWith);
            rWithout = Math.max(rWithout, rightInfo.rootWithout);
        }

        return new Info(rWithout,rWith);
    }


}
